1. Field of the Invention
The present invention relates to the field of integrated circuit (IC) design. More specifically, the present invention relates to an improved method for generating optimized floorplans for design blocks, using ceiling and floor contours on an O-tree structure.
2. Background Information
As the complexity of IC design continues to increase, pre-existing design hierarchies or design blocks are increasingly being "re-used" to simplify the design task. Floorplanning or building block placement is becoming critical to the performance of the hierarchical design process.
In the case of floorplan with slicing structure, it is known to use a binary tree representation to perform the building block placement operation. The leaves of the binary tree correspond to the blocks and each internal node defines a vertical or horizontal merge operation of its two descendents. The number of possible configurations for the tree, and therefore the extent of computation is in the order of O(n!2.sup.5n-3 /n.sup.1.5). There have been efforts to identify the redundancy among the possible configurations, and thereby reducing the amount of computation. See e.g. D. F. Wong, and C. L. Lin, A New Algorithm for Floorplan Design, DAC, pp. 101-107, 1986.
Efforts have also been made to extend the binary tree representation to floorplan with non-slicing structure. See e.g. P. Pan and C. L. Liu, Area Minimization for Floorplans, IEEE Transactions on Computer-Aided Design of Integrated Circuits and System, pp. 123-132, January, 1995; and T. C. Wang, and D. F. Wong, An Optimal Algorithm for Floorplan Area Optimization, DAC, pp. 180-186, 1990. However, the performance of these approaches have been less desirable.
Onodera et al. further classify topological relationship between two blocks in a floorplan with non-slicing structure into four classes, and use branch-and-bound method to solve the problem. See H. Onodera, Y. Taniguchi, K. Tamaru, Branch-and-Bound Placement for Building Block Layout, DAC, pp. 433-439, 1991. The disadvantage of the approach is that the solution space is still in the order of O(2.sup.n(n+2)), which is too complicated even for today's high performance computers.
Sequence pair and bounded slicing grid have been introduced the reduce the solution space for the floorplan with non-slicing structure problem. See e.g. H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajatani, Rectangular-Packing-Based Module Placement, ICCAD, pp. 472-479, 1995; and S. Nakatake, K. Fujiyoshi, H. Murata, and Y. Kajatani, Module Placement on BSG-Structure and IC Layout Application, ICCAD, pp. 484-491, 1996. The two approaches are different representations, but they are all basically based on constraint graph to manipulate the transformation between the representation and their placement, which unfortunately also requires intensive amount of computation. When using the sequence pair representation, two sets of permutations are employed to present the geometric relations of the blocks. The possible configurations are in the order of O((n!).sup.2). From sequence pair to its placement, the transformation operation takes O(n log n) time. See e.g. T. Takahasi, An Algorithm for Finding a Maximum-Weight Decreasing in a Permutation, Motivated by Rectangle Packing Problem, IEICE, vol. VLD96, pp. 31-35, 1996. When using the bounded slicing grid approach, an n by n grid plane is used for placement of n blocks. The representation itself has much dependency, one floorplan could have several choices of representations, resulting inefficient and wasteful computation.
An iterative approach employing cluster refinement has also been proposed to optimize area and interconnection. See e.g. J. Xu, P.N. Guo, and C.K. Cheng, Cluster Refinement for Block Placement, DAC, pp. 762-765, 1997. For small cluster sizes (k), the run time complexity for each iteration is in the order of O(n.sup.2+k/2). However, for larger cluster sizes, the approach is too CPU-intensive and difficult to handle.
Finally, most recently, Guo and Cheng have devised an ordered tree (O-tree) structure to represent placement of design blocks. A deterministic approach was developed to search for an O-tree representation that corresponds to an optimal placement. Under te deterministic approach, design blocks and candidate "reinsertion" points are systematically analyzed with respect to a cost function to find the optimal placement. Experience has shown the deterministic approach to be still too time consuming.
Thus, an improved approach to design block placement and floorplan generation is desired.
Note: The concept of O-tree and the deterministic approach to seeking the optimal placement will be the subject of a presentation in the upcoming Design Automation Conference, Jun. 21-25, 1999, accordingly published as part of the Proceedings of the conference in a future day. The concept of O-tree and the deterministic approach is thus also explained as foundational materials in the description of the improved approach of the present invention to follow.